package com.berchen.offer;

/**
 * 给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。
 * 1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点
 * 2.叶子节点是指没有子节点的节点
 * 3.路径只能从父节点到子节点，不能从子节点到父节点
 * 4.总节点数目为n
 */
public class Test05 {
    public static void main(String[] args) {
        TreeNode root=new TreeNode(8);
        TreeNode node6=new TreeNode(6);
        TreeNode node10=new TreeNode(10);
        TreeNode node5=new TreeNode(5);
        TreeNode node7=new TreeNode(7);
        TreeNode node9=new TreeNode(9);
        TreeNode node11=new TreeNode(11);
        node6.left=node5;
        node6.right=node7;
        node10.left=node9;
        node10.right=node11;
        root.left=node6;
        root.right=node10;

        Test05 test05 = new Test05();
        System.out.println(test05.hasPathSum(root, 30));
    }
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root==null){
            return false;
        }
        return diGui(root,sum, 0);
    }
    public boolean diGui(TreeNode node,int sum,int value){
        if(node==null){
            return false;
        }
        value=value+ node.val;
        // 这是叶子节点
        if(node.left==null&&node.right==null){
            if(sum==value){
                return true;
            }
        }

        boolean flag=diGui(node.left,sum,value);
        if(!flag){
            flag=diGui(node.right,sum,value);
        }
        return flag;
    }
}
